/*================================================================
*   Copyright (C) 2023 baichao All rights reserved.
*
*   文件名称：maxheap.c
*   创 建 者：baichao
*   创建日期：2023年12月17日
*   描    述：
*
================================================================*/

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int* heapArray;
  int size;
  int capacity;
} MaxHeap;

MaxHeap* createMaxHeap(int capacity) {
  MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
  heap->heapArray = (int*)malloc(capacity * sizeof(int));
  heap->size = 0;
  heap->capacity = capacity;
  return heap;
}

void siftUp(MaxHeap* heap, int index) {
  int parentIndex, temp;
  if (index != 0) {
    parentIndex = (index - 1) / 2;
    if (heap->heapArray[parentIndex] < heap->heapArray[index]) {
      temp = heap->heapArray[parentIndex];
      heap->heapArray[parentIndex] = heap->heapArray[index];
      heap->heapArray[index] = temp;
      siftUp(heap, parentIndex);
    }
  }
}

void siftDown(MaxHeap* heap, int index) {
  int leftChildIndex, rightChildIndex, maxIndex, temp;
  leftChildIndex = 2 * index + 1;
  rightChildIndex = 2 * index + 2;
  if (rightChildIndex >= heap->size) {
    if (leftChildIndex >= heap->size) {
      return;
    } else {
      maxIndex = leftChildIndex;
    }
  } else {
    if (heap->heapArray[leftChildIndex] >= heap->heapArray[rightChildIndex]) {
      maxIndex = leftChildIndex;
    } else {
      maxIndex = rightChildIndex;
    }
  }
  if (heap->heapArray[index] < heap->heapArray[maxIndex]) {
    temp = heap->heapArray[index];
    heap->heapArray[index] = heap->heapArray[maxIndex];
    heap->heapArray[maxIndex] = temp;
    siftDown(heap, maxIndex);
  }
}

void insert(MaxHeap* heap, int value) {
  if (heap->size == heap->capacity) {
    printf("Heap is full. Cannot insert more elements.\n");
    return;
  }
  heap->heapArray[heap->size] = value;
  siftUp(heap, heap->size);
  heap->size++;
}

int deleteMax(MaxHeap* heap) {
  if (heap->size == 0) {
    printf("Heap is empty. Cannot delete any element.\n");
    return -1;
  }
  int max = heap->heapArray[0];
  heap->heapArray[0] = heap->heapArray[heap->size - 1];
  heap->size--;
  siftDown(heap, 0);
  return max;
}

void printHeap(MaxHeap* heap) {
  printf("Heap: ");
  for (int i = 0; i < heap->size; i++) {
    printf("%d ", heap->heapArray[i]);
  }
  printf("\n");
}

int main() {
  MaxHeap* heap = createMaxHeap(10);
  insert(heap, 5);
  insert(heap, 8);
  insert(heap, 3);
  insert(heap, 10);
  insert(heap, 2);
  printHeap(heap);
  printf("Max element: %d\n", deleteMax(heap));
  printHeap(heap);
  return 0;
}
